#include "completebinarytreewindow.h"
#include <QPainter>
#include <QDialog>
#include <QDialogButtonBox>
#include <QVBoxLayout>
#include <QFormLayout>
#include <QTime>
#include <cmath>

// ArrayVisualizationWidget 的实现
ArrayVisualizationWidget::ArrayVisualizationWidget(QWidget *parent)
    : QWidget(parent), m_currentTraverseIndex(-1), m_arraySize(0), m_isTraversing(false)
{
}

void ArrayVisualizationWidget::setArray(const IntArray& array) {
    m_array = array;
    m_arraySize = array.size();
    update();
}

void ArrayVisualizationWidget::paintEvent(QPaintEvent* event)
{
    Q_UNUSED(event);

    QPainter painter(this);
    painter.setRenderHint(QPainter::Antialiasing);
    painter.setPen(QPen(Qt::black, 2));

    QFont font = painter.font();
    font.setPointSize(10);
    painter.setFont(font);

    painter.fillRect(rect(), Qt::white);

    if (m_array.empty()) {
        painter.drawText(rect(), Qt::AlignCenter, "完全二叉树为空");
        return;
    }

    // 绘制数组标题
    painter.drawText(50, 30, "完全二叉树顺序存储数组:");

    // 绘制数组元素
    for (int i = 0; i < m_arraySize; i++) {
        int x = 50 + i * 80;
        int y = 50;

        bool isHighlighted = m_isTraversing && (i == m_currentTraverseIndex);
        drawArrayElement(painter, m_array[i], i, x, y, isHighlighted);
    }

    // 绘制索引标记
    painter.setPen(QPen(Qt::darkGray, 1));
    for (int i = 0; i < m_arraySize; i++) {
        int x = 50 + i * 80;
        int y = 150;
        painter.drawText(QRect(x, y, 60, 30), Qt::AlignCenter, QString("索引:%1").arg(i));
    }
}

void ArrayVisualizationWidget::drawArrayElement(QPainter& painter, int value, int index, int x, int y, bool isHighlighted)
{
    // 设置元素样式
    if (isHighlighted) {
        painter.setBrush(QBrush(QColor(255, 255, 0))); // 黄色高亮
        painter.setPen(QPen(Qt::red, 3));
    } else {
        painter.setBrush(QBrush(Qt::white));
        painter.setPen(QPen(Qt::black, 2));
    }

    // 绘制数组元素框
    QRect elementRect(x, y, 60, 60);
    painter.drawRect(elementRect);

    // 绘制索引小标
    painter.setPen(QPen(Qt::blue, 1));
    QRect indexRect(x, y - 20, 60, 20);
    painter.drawText(indexRect, Qt::AlignCenter, QString("[%1]").arg(index));

    // 绘制数据值
    painter.setPen(QPen(Qt::black, 2));
    painter.drawText(elementRect, Qt::AlignCenter, QString::number(value));

    // 绘制父子关系指示
    if (index > 0) {
        painter.setPen(QPen(Qt::green, 1, Qt::DashLine));

        if (index % 2 == 1) {
            // 左孩子
            painter.drawText(x + 30, y - 5, "←左孩子");
        } else {
            // 右孩子
            painter.drawText(x + 30, y - 5, "→右孩子");
        }
    }
}

QSize ArrayVisualizationWidget::getArraySize() const {
    int width = m_arraySize * 80 + 100;
    int height = 200;
    return QSize(width, height);
}

void ArrayVisualizationWidget::startTraversal(const IntArray& order) {
    m_traverseOrder = order;
    m_currentTraverseIndex = -1; // 从-1开始，这样第一次next会到0
    m_isTraversing = true;
    update();
}

void ArrayVisualizationWidget::nextTraversalStep() {
    if (!m_isTraversing) return;

    if (m_currentTraverseIndex < m_traverseOrder.size() - 1) {
        m_currentTraverseIndex++;
        update();

        // 发出信号，传递当前遍历结果
        QString result;
        for (int i = 0; i <= m_currentTraverseIndex && i < m_traverseOrder.size(); i++) {
            if (i > 0) result += " ";
            result += QString::number(m_traverseOrder[i]);
        }
        emit traversalStepCompleted(result);

        // 检查是否是最后一步
        if (m_currentTraverseIndex >= m_traverseOrder.size() - 1) {
            m_isTraversing = false;
            emit traversalFinished();
        }
    } else {
        m_isTraversing = false;
        emit traversalFinished();
    }
}

void ArrayVisualizationWidget::resetTraversal() {
    m_currentTraverseIndex = -1;
    m_traverseOrder.clear();
    m_isTraversing = false;
    update();
}

// CompleteBinaryTreeWindow 的实现
CompleteBinaryTreeWindow::CompleteBinaryTreeWindow(QWidget *parent)
    : QMainWindow(parent), m_isTraversing(false), m_traverseSpeed(800)
{
    setupUI();
    updateDisplay();

    // 初始化遍历定时器
    m_traverseTimer = new QTimer(this);
    connect(m_traverseTimer, &QTimer::timeout, this, [this]() {
        if (m_visualizationWidget->isTraversing()) {
            m_visualizationWidget->nextTraversalStep();
        } else {
            m_traverseTimer->stop();
            m_isTraversing = false;
            updateDisplay();
        }
    });
}

CompleteBinaryTreeWindow::~CompleteBinaryTreeWindow()
{
    // 确保定时器停止
    if (m_traverseTimer && m_traverseTimer->isActive()) {
        m_traverseTimer->stop();
    }
}

void CompleteBinaryTreeWindow::setupUI()
{
    setWindowTitle("完全二叉树顺序存储可视化演示");
    setMinimumSize(1200, 700);
    resize(1200, 700);

    QWidget *centralWidget = new QWidget(this);
    setCentralWidget(centralWidget);

    QHBoxLayout *mainLayout = new QHBoxLayout(centralWidget);

    // 左侧：可视化部分
    QVBoxLayout *leftLayout = new QVBoxLayout();
    QLabel *visualLabel = new QLabel("完全二叉树顺序存储可视化:");
    visualLabel->setStyleSheet("font-weight: bold; font-size: 14px;");

    m_scrollArea = new QScrollArea();
    m_scrollArea->setWidgetResizable(true);
    m_scrollArea->setHorizontalScrollBarPolicy(Qt::ScrollBarAsNeeded);
    m_scrollArea->setVerticalScrollBarPolicy(Qt::ScrollBarAsNeeded);
    m_scrollArea->setMinimumSize(900, 650);

    m_visualizationWidget = new ArrayVisualizationWidget();
    connect(m_visualizationWidget, &ArrayVisualizationWidget::traversalStepCompleted,
            this, &CompleteBinaryTreeWindow::onTraversalStepCompleted);
    connect(m_visualizationWidget, &ArrayVisualizationWidget::traversalFinished,
            this, &CompleteBinaryTreeWindow::onTraversalFinished);
    m_scrollArea->setWidget(m_visualizationWidget);

    leftLayout->addWidget(visualLabel);
    leftLayout->addWidget(m_scrollArea);
    mainLayout->addLayout(leftLayout, 3);

    // 右侧：操作和信息部分
    QVBoxLayout *rightLayout = new QVBoxLayout();
    rightLayout->setSpacing(15);

    QWidget *rightPanel = new QWidget();
    rightPanel->setLayout(rightLayout);
    rightPanel->setMaximumWidth(300);

    // 返回按钮
    QPushButton *returnBtn = new QPushButton("返回主菜单");
    returnBtn->setStyleSheet("QPushButton { background-color: #f0f0f0; border: 1px solid #ccc; padding: 8px; }");
    rightLayout->addWidget(returnBtn);

    // 操作按钮组
    QGroupBox *opsGroup = new QGroupBox("操作面板");
    opsGroup->setStyleSheet("QGroupBox { font-weight: bold; }");
    QVBoxLayout *opsLayout = new QVBoxLayout(opsGroup);
    opsLayout->setSpacing(10);

    QPushButton *inputBtn = new QPushButton("构建完全二叉树");
    inputBtn->setToolTip("点击输入层次遍历序列构建完全二叉树");
    inputBtn->setMinimumHeight(35);

    QPushButton *insertBtn = new QPushButton("插入节点");
    insertBtn->setToolTip("点击在完全二叉树末尾插入节点");
    insertBtn->setMinimumHeight(35);

    QPushButton *deleteBtn = new QPushButton("删除末尾节点");
    deleteBtn->setToolTip("点击删除完全二叉树末尾节点");
    deleteBtn->setMinimumHeight(35);

    // 遍历操作
    QGroupBox *traverseGroup = new QGroupBox("遍历操作");
    QVBoxLayout *traverseLayout = new QVBoxLayout(traverseGroup);
    m_traverseCombo = new QComboBox();
    m_traverseCombo->addItem("前序遍历");
    m_traverseCombo->addItem("中序遍历");
    m_traverseCombo->addItem("后序遍历");
    m_traverseCombo->addItem("层次遍历");

    // 遍历速度控制
    QHBoxLayout *speedLayout = new QHBoxLayout();
    QLabel *speedLabel = new QLabel("速度:");
    QComboBox *speedCombo = new QComboBox();
    speedCombo->addItem("慢速", 1500);
    speedCombo->addItem("中速", 800);
    speedCombo->addItem("快速", 400);
    speedCombo->setCurrentIndex(1); // 默认中速

    // 连接速度选择信号
    connect(speedCombo, QOverload<int>::of(&QComboBox::currentIndexChanged), [this, speedCombo](int index) {
        m_traverseSpeed = speedCombo->itemData(index).toInt();
        if (m_isTraversing) {
            m_traverseTimer->stop();
            m_traverseTimer->start(m_traverseSpeed);
        }
    });

    speedLayout->addWidget(speedLabel);
    speedLayout->addWidget(speedCombo);

    QPushButton *traverseBtn = new QPushButton("执行遍历");
    traverseBtn->setMinimumHeight(35);

    traverseLayout->addWidget(m_traverseCombo);
    traverseLayout->addLayout(speedLayout);
    traverseLayout->addWidget(traverseBtn);

    // 其他操作按钮
    QPushButton *clearBtn = new QPushButton("清空二叉树");
    clearBtn->setMinimumHeight(35);
    QPushButton *randomBtn = new QPushButton("生成随机二叉树");
    randomBtn->setMinimumHeight(35);

    // 将所有按钮添加到操作面板
    opsLayout->addWidget(inputBtn);
    opsLayout->addWidget(insertBtn);
    opsLayout->addWidget(deleteBtn);
    opsLayout->addWidget(traverseGroup);

    QHBoxLayout *otherOpsLayout = new QHBoxLayout();
    otherOpsLayout->addWidget(clearBtn);
    otherOpsLayout->addWidget(randomBtn);
    opsLayout->addLayout(otherOpsLayout);

    // 信息显示部分
    QGroupBox *infoGroup = new QGroupBox("完全二叉树信息");
    infoGroup->setStyleSheet("QGroupBox { font-weight: bold; }");
    QVBoxLayout *infoLayout = new QVBoxLayout(infoGroup);
    m_display = new QTextEdit();
    m_display->setReadOnly(true);
    m_display->setMaximumHeight(400);
    infoLayout->addWidget(m_display);

    // 将操作面板和信息显示添加到右侧布局
    rightLayout->addWidget(opsGroup);
    rightLayout->addWidget(infoGroup);

    // 添加右侧面板到主布局
    mainLayout->addWidget(rightPanel, 1);

    // 连接信号槽
    connect(inputBtn, &QPushButton::clicked, this, &CompleteBinaryTreeWindow::onInputData);
    connect(insertBtn, &QPushButton::clicked, this, &CompleteBinaryTreeWindow::onInsert);
    connect(deleteBtn, &QPushButton::clicked, this, &CompleteBinaryTreeWindow::onDelete);
    connect(traverseBtn, &QPushButton::clicked, this, &CompleteBinaryTreeWindow::onTraverse);
    connect(clearBtn, &QPushButton::clicked, this, &CompleteBinaryTreeWindow::onClear);
    connect(randomBtn, &QPushButton::clicked, this, &CompleteBinaryTreeWindow::onGenerateRandom);
    connect(returnBtn, &QPushButton::clicked, this, &CompleteBinaryTreeWindow::onReturnToMainMenu);
}

void CompleteBinaryTreeWindow::onReturnToMainMenu()
{
    // 停止定时器
    if (m_traverseTimer && m_traverseTimer->isActive()) {
        m_traverseTimer->stop();
    }

    emit returnToMainMenu();
    this->close();
}

void CompleteBinaryTreeWindow::updateDisplay()
{
    QString info = QString("完全二叉树信息\n\n节点数: %1\n树的高度: %2\n\n").arg(m_treeData.size()).arg(getTreeHeight());

    if (m_treeData.empty()) {
        info += "完全二叉树为空";
    } else {
        info += "数组存储: [";
        for (int i = 0; i < m_treeData.size(); i++) {
            if (i > 0) info += ", ";
            info += QString::number(m_treeData[i]);
        }
        info += "]\n\n";

        info += "层次遍历结果: ";
        IntArray levelOrder;
        levelOrderTraversal(levelOrder);
        for (int i = 0; i < levelOrder.size(); i++) {
            info += QString::number(levelOrder[i]) + " ";
        }
        info += "\n\n";

        info += "前序遍历: ";
        IntArray preorder;
        preorderTraversal(0, preorder);
        for (int i = 0; i < preorder.size(); i++) {
            info += QString::number(preorder[i]) + " ";
        }
        info += "\n\n";

        info += "中序遍历: ";
        IntArray inorder;
        inorderTraversal(0, inorder);
        for (int i = 0; i < inorder.size(); i++) {
            info += QString::number(inorder[i]) + " ";
        }
        info += "\n\n";

        info += "后序遍历: ";
        IntArray postorder;
        postorderTraversal(0, postorder);
        for (int i = 0; i < postorder.size(); i++) {
            info += QString::number(postorder[i]) + " ";
        }

        // 如果正在遍历，显示当前遍历结果
        if (m_isTraversing) {
            info += "\n\n=== 当前遍历过程 ===\n";
            info += m_currentTraverseResult;
        }
    }

    m_display->setText(info);
    m_visualizationWidget->setArray(m_treeData);

    // 调整可视化部件大小
    QSize arraySize = m_visualizationWidget->getArraySize();
    m_visualizationWidget->setFixedSize(arraySize);
}

int CompleteBinaryTreeWindow::getTreeHeight() const
{
    if (m_treeData.empty()) return 0;

    int n = m_treeData.size();
    int height = 0;
    while ((1 << height) - 1 < n) {
        height++;
    }
    return height;
}

void CompleteBinaryTreeWindow::preorderTraversal(int index, IntArray& result)
{
    if (index >= m_treeData.size()) return;

    result.push_back(m_treeData[index]); // 访问根节点
    preorderTraversal(getLeftChildIndex(index), result); // 遍历左子树
    preorderTraversal(getRightChildIndex(index), result); // 遍历右子树
}

void CompleteBinaryTreeWindow::inorderTraversal(int index, IntArray& result)
{
    if (index >= m_treeData.size()) return;

    inorderTraversal(getLeftChildIndex(index), result); // 遍历左子树
    result.push_back(m_treeData[index]); // 访问根节点
    inorderTraversal(getRightChildIndex(index), result); // 遍历右子树
}

void CompleteBinaryTreeWindow::postorderTraversal(int index, IntArray& result)
{
    if (index >= m_treeData.size()) return;

    postorderTraversal(getLeftChildIndex(index), result); // 遍历左子树
    postorderTraversal(getRightChildIndex(index), result); // 遍历右子树
    result.push_back(m_treeData[index]); // 访问根节点
}

void CompleteBinaryTreeWindow::levelOrderTraversal(IntArray& result)
{
    result = m_treeData; // 对于完全二叉树，层次遍历就是数组顺序
}

int CompleteBinaryTreeWindow::randomInt(int min, int max)
{
    static bool seeded = false;
    if (!seeded) {
        srand(QTime::currentTime().msec());
        seeded = true;
    }
    return min + (rand() % (max - min + 1));
}

void CompleteBinaryTreeWindow::onTraversalStepCompleted(const QString& currentResult)
{
    m_currentTraverseResult = currentResult;
    updateDisplay();
}

void CompleteBinaryTreeWindow::onTraversalFinished()
{
    m_traverseTimer->stop();
    m_isTraversing = false;
    updateDisplay();
    QMessageBox::information(this, "遍历完成", "遍历过程已完成！");
}

void CompleteBinaryTreeWindow::onInputData()
{
    QDialog dialog(this);
    dialog.setWindowTitle("构建完全二叉树");
    dialog.setFixedSize(400, 150);

    QVBoxLayout *mainLayout = new QVBoxLayout(&dialog);

    QLabel *label = new QLabel("请输入层次遍历序列（用空格分隔）:");
    QLineEdit *edit = new QLineEdit();
    edit->setPlaceholderText("例如: 1 2 3 4 5 6 7");

    QDialogButtonBox *buttons = new QDialogButtonBox(QDialogButtonBox::Ok | QDialogButtonBox::Cancel);

    mainLayout->addWidget(label);
    mainLayout->addWidget(edit);
    mainLayout->addWidget(buttons);

    connect(buttons, &QDialogButtonBox::accepted, &dialog, &QDialog::accept);
    connect(buttons, &QDialogButtonBox::rejected, &dialog, &QDialog::reject);

    if (dialog.exec() == QDialog::Accepted) {
        QString input = edit->text();
        if (input.isEmpty()) {
            QMessageBox::warning(this, "输入错误", "请输入有效的层次遍历序列");
            return;
        }

        // 停止遍历
        if (m_isTraversing) {
            m_traverseTimer->stop();
            m_visualizationWidget->resetTraversal();
            m_isTraversing = false;
        }

        m_treeData.clear();

        QStringList numbers = input.split(' ', Qt::SkipEmptyParts);

        for (const QString& numStr : numbers) {
            bool ok;
            int value = numStr.toInt(&ok);
            if (ok) {
                m_treeData.push_back(value);
            } else {
                QMessageBox::warning(this, "输入错误", QString("'%1' 不是有效的整数").arg(numStr));
                m_treeData.clear();
                return;
            }
        }

        updateDisplay();
        QMessageBox::information(this, "构建成功", QString("成功构建包含 %1 个节点的完全二叉树").arg(m_treeData.size()));
    }
}

void CompleteBinaryTreeWindow::onInsert()
{
    QDialog dialog(this);
    dialog.setWindowTitle("插入节点");
    dialog.setFixedSize(300, 120);

    QVBoxLayout *mainLayout = new QVBoxLayout(&dialog);

    QLabel *label = new QLabel("请输入要插入的值:");
    QLineEdit *edit = new QLineEdit();
    edit->setPlaceholderText("整数");

    QDialogButtonBox *buttons = new QDialogButtonBox(QDialogButtonBox::Ok | QDialogButtonBox::Cancel);

    mainLayout->addWidget(label);
    mainLayout->addWidget(edit);
    mainLayout->addWidget(buttons);

    connect(buttons, &QDialogButtonBox::accepted, &dialog, &QDialog::accept);
    connect(buttons, &QDialogButtonBox::rejected, &dialog, &QDialog::reject);

    if (dialog.exec() == QDialog::Accepted) {
        QString input = edit->text();
        if (input.isEmpty()) {
            QMessageBox::warning(this, "输入错误", "请输入要插入的值");
            return;
        }

        bool ok;
        int value = input.toInt(&ok);
        if (ok) {
            // 停止遍历
            if (m_isTraversing) {
                m_traverseTimer->stop();
                m_visualizationWidget->resetTraversal();
                m_isTraversing = false;
            }

            m_treeData.push_back(value);
            updateDisplay();
            QMessageBox::information(this, "插入成功", QString("节点 %1 已插入到完全二叉树末尾").arg(value));
        } else {
            QMessageBox::warning(this, "输入错误", "请输入有效的整数");
        }
    }
}

void CompleteBinaryTreeWindow::onDelete()
{
    if (m_treeData.empty()) {
        QMessageBox::information(this, "删除失败", "完全二叉树为空，无法删除");
        return;
    }

    QMessageBox::StandardButton reply;
    reply = QMessageBox::question(this, "确认删除", "确定要删除末尾节点吗？",
                                  QMessageBox::Yes | QMessageBox::No);
    if (reply == QMessageBox::Yes) {
        // 停止遍历
        if (m_isTraversing) {
            m_traverseTimer->stop();
            m_visualizationWidget->resetTraversal();
            m_isTraversing = false;
        }

        int deletedValue = m_treeData.back();
        m_treeData.erase(m_treeData.size() - 1);
        updateDisplay();
        QMessageBox::information(this, "删除成功", QString("节点 %1 已删除").arg(deletedValue));
    }
}

void CompleteBinaryTreeWindow::onTraverse()
{
    if (m_treeData.empty()) {
        QMessageBox::information(this, "遍历结果", "完全二叉树为空");
        return;
    }

    // 停止之前的遍历
    if (m_isTraversing) {
        m_traverseTimer->stop();
        m_visualizationWidget->resetTraversal();
        m_isTraversing = false;
    }

    QString traverseType = m_traverseCombo->currentText();
    IntArray traverseOrder;

    if (traverseType == "前序遍历") {
        preorderTraversal(0, traverseOrder);
    } else if (traverseType == "中序遍历") {
        inorderTraversal(0, traverseOrder);
    } else if (traverseType == "后序遍历") {
        postorderTraversal(0, traverseOrder);
    } else if (traverseType == "层次遍历") {
        levelOrderTraversal(traverseOrder);
    }

    // 开始可视化遍历
    m_isTraversing = true;
    m_currentTraverseResult = "";
    m_visualizationWidget->startTraversal(traverseOrder);
    m_traverseTimer->start(m_traverseSpeed);
}

void CompleteBinaryTreeWindow::onClear()
{
    QMessageBox::StandardButton reply;
    reply = QMessageBox::question(this, "确认清空", "确定要清空完全二叉树吗？",
                                  QMessageBox::Yes | QMessageBox::No);
    if (reply == QMessageBox::Yes) {
        // 停止遍历
        if (m_isTraversing) {
            m_traverseTimer->stop();
            m_visualizationWidget->resetTraversal();
            m_isTraversing = false;
        }

        m_treeData.clear();
        updateDisplay();
        QMessageBox::information(this, "清空成功", "完全二叉树已清空");
    }
}

void CompleteBinaryTreeWindow::onGenerateRandom()
{
    QMessageBox::StandardButton reply;
    reply = QMessageBox::question(this, "生成随机完全二叉树",
                                  "确定要生成随机完全二叉树吗？这将替换当前二叉树。",
                                  QMessageBox::Yes | QMessageBox::No);
    if (reply == QMessageBox::Yes) {
        // 停止遍历
        if (m_isTraversing) {
            m_traverseTimer->stop();
            m_visualizationWidget->resetTraversal();
            m_isTraversing = false;
        }

        m_treeData.clear();

        int nodeCount = randomInt(5, 15);
        for (int i = 0; i < nodeCount; i++) {
            m_treeData.push_back(randomInt(1, 100));
        }

        updateDisplay();
        QMessageBox::information(this, "生成成功", QString("已生成包含 %1 个节点的随机完全二叉树").arg(nodeCount));
    }
}
